{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Subarrays With Fixed Bounds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #sliding-window #monotonic-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #滑动窗口 #单调队列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计定界子数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数 <code>minK</code> 以及 <code>maxK</code> 。</p>\n",
    "\n",
    "<p><code>nums</code> 的定界子数组是满足下述条件的一个子数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子数组中的 <strong>最小值</strong> 等于 <code>minK</code> 。</li>\n",
    "\t<li>子数组中的 <strong>最大值</strong> 等于 <code>maxK</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回定界子数组的数目。</p>\n",
    "\n",
    "<p>子数组是数组中的一个连续部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,5,2,7,5], minK = 1, maxK = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>定界子数组是 [1,3,5] 和 [1,3,5,2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,1,1], minK = 1, maxK = 1\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>nums 的每个子数组都是一个定界子数组。共有 10 个子数组。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], minK, maxK &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-subarrays-with-fixed-bounds](https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-subarrays-with-fixed-bounds](https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,2,7,5]\\n1\\n5', '[1,1,1,1]\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        sisa_lens: List[int] = []\n",
    "        sisa_len: int = 1\n",
    "            \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                sisa_len += 1\n",
    "            else:\n",
    "                sisa_lens.append(sisa_len)\n",
    "                sisa_len = 1\n",
    "        sisa_lens.append(sisa_len)\n",
    "        \n",
    "        return sum((1 + n) * n // 2 for n in sisa_lens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, res = 1,1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                cur = 1\n",
    "            else:\n",
    "                cur+=1\n",
    "            res+=cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        temp = 0\n",
    "        allTemp = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                temp = 0\n",
    "            else:\n",
    "                temp += 1\n",
    "            allTemp += temp + 1\n",
    "        return allTemp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        final_count = 1\n",
    "        count = 1\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] > nums[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 1\n",
    "            final_count += count\n",
    "        return final_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        res, i = n, 0\n",
    "        while i < n:\n",
    "            j, cnt = i, 0\n",
    "            while j + 1 < n and nums[j] < nums[j + 1]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            res += cnt + cnt * (cnt - 1) // 2\n",
    "            i = j + 1\n",
    "        return res            \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "      a = 0\n",
    "      b = 0\n",
    "      pre = inf\n",
    "      for num in nums:\n",
    "        if num > pre: a += 1\n",
    "        else: a = 1\n",
    "        pre = num\n",
    "        b += a\n",
    "      return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        res = dp = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            dp = dp + 1 if i == 0 or num > nums[i - 1] else 1\n",
    "            res += dp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\r\n",
    "        count = 1\r\n",
    "        pre = 1\r\n",
    "        for i in range(1, len(nums)):\r\n",
    "            if nums[i] > nums[i - 1]:\r\n",
    "                pre += 1\r\n",
    "            else:\r\n",
    "                pre = 1\r\n",
    "            count += pre\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        result, cur, prev = 0, 0, float('inf')\n",
    "        for x in nums:\n",
    "            result += (cur := cur + 1 if prev < x else 1)\n",
    "            prev = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        cur, pre = 0, float('inf')\n",
    "        return sum((cur := cur + 1 if (-pre + (pre := x)) > 0 else 1) for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "            count += pre\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1  # 因为数组的第一个元素自身就是一个子数组\n",
    "        pre = 1  # 记录前一个数字的严格递增子数组的长度\n",
    "\n",
    "        # 从数组的第二个元素开始遍历\n",
    "        for i in range(1, len(nums)):\n",
    "            # 如果当前元素大于前一个元素，说明它可以构成新的递增子数组\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            # 否则，重置 pre 为1\n",
    "            else:\n",
    "                pre = 1\n",
    "            # 累加 pre 到 count\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "# 示例\n",
    "solution = Solution()\n",
    "nums1 = [1,3,5,4,4,6]\n",
    "print(solution.countSubarrays(nums1))  # 输出: 10\n",
    "\n",
    "nums2 = [1,2,3,4,5]\n",
    "print(solution.countSubarrays(nums2))  # 输出: 15\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍利\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        pre = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = 1\n",
    "\n",
    "            count += pre\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def countSubarrays1(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # 遍历2\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 1\n",
    "        cur = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > nums[i - 1]:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            count += cur\n",
    "\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 便利\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        cur = 1\n",
    "        for x,y in pairwise(nums):\n",
    "            if y > x:\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = 1\n",
    "\n",
    "            ans += cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "\n",
    "        \n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=max(dp[i],dp[i-1]+1)\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            else:\n",
    "                dp[i]=1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]+=dp[i-1]\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #因为有无后效性,线性DP即可\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int]) -> int:\n",
    "        #DP\n",
    "        n=len(nums)\n",
    "        dp=[1]*n\n",
    "        ans=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans =0\n",
    "        min_i =max_i =i0=-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                min_i =i\n",
    "            if x==maxK:\n",
    "                max_i = i\n",
    "            if not minK<=x<=maxK:\n",
    "                i0=i\n",
    "\n",
    "            ans+= max(min(min_i,max_i)-i0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        # 双指针：\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        res = 0\n",
    "        min_i,max_i,i0 = -1,-1,-1\n",
    "        for i,x in enumerate(nums):\n",
    "            # 记录下最近出现过的minK和maxK位置\n",
    "            if x == minK : \n",
    "                min_i = i\n",
    "            if x == maxK:\n",
    "                max_i = i\n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i\n",
    "            # 如果min(min_i,max_i)-io < 0,则说明在i0右侧minK和maxK没有同时出现\n",
    "            # 综上max(min(max_i,max_i) - i0, 0)表示的是以i为右端点的符合条件的子数组\n",
    "            res += max(min(min_i,max_i) - i0, 0)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "            # if j > i0: ans += j - i0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        minn, maxx = -1, -1\n",
    "        ans = 0\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                minn = i\n",
    "            if x == maxK:\n",
    "                maxx = i\n",
    "            if x < minK or x > maxK:\n",
    "                pre = i + 1\n",
    "            ans += max(0, min(minn, maxx) - pre + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        start_point = 0\n",
    "        idx = ans = 0\n",
    "        min_pos = max_pos = -1\n",
    "\n",
    "        while idx < n:\n",
    "            if nums[idx] < minK or nums[idx] > maxK:\n",
    "                idx += 1\n",
    "                start_point = idx\n",
    "                continue\n",
    "            if nums[idx] == minK:\n",
    "                min_pos = idx\n",
    "            if nums[idx] == maxK:\n",
    "                max_pos = idx\n",
    "            ans += max(min(min_pos, max_pos) - start_point + 1, 0)\n",
    "            idx += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minI = -1\n",
    "        maxI = -1\n",
    "        curI = -1\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            val = nums[i]\n",
    "            if val > maxK or val < minK:\n",
    "                curI = i\n",
    "\n",
    "            if val == maxK:\n",
    "                maxI = i\n",
    "\n",
    "            if val == minK:\n",
    "                minI = i\n",
    "\n",
    "            ans += max(min(maxI, minI) - curI, 0)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        offMinK = offMaxK = -1\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if n < minK or n > maxK:\n",
    "                left = i + 1\n",
    "            else:\n",
    "                if n == minK:\n",
    "                    offMinK = i\n",
    "                if n == maxK:\n",
    "                    offMaxK = i\n",
    "            if left <= min(offMinK, offMaxK):\n",
    "                res += min(offMinK, offMaxK) - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                min_i = i \n",
    "            if x == maxK:\n",
    "                max_i = i \n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i \n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        l = minI = maxI = -1\n",
    "        count = 0 \n",
    "        for i , num in enumerate(nums):\n",
    "            if num > maxK or num < minK: l = i \n",
    "            if num == maxK : maxI = i \n",
    "            if num == minK : minI = i \n",
    "            \n",
    "            count += max(min(minI, maxI) - l , 0) \n",
    "            \n",
    "\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# count子数组\n",
    "# 枚举右端点作为子区间右端点的情况 \n",
    "# 将使区间不符合性质的上一个点作为左端点\n",
    "# 判断在这种情况下从左端点到右端点符合性质的子区间个数\n",
    "# 有两个性质点 所以需要两个下标来统计\n",
    "# 两个性质点如果有一个小于左端点 那么则个数为0 如果都大于左端点 那么则为小的那个减去左端点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        r1=-1\n",
    "        r2=-1\n",
    "        l=-1\n",
    "        ans=0\n",
    "        for i,v in enumerate(nums):\n",
    "            if v==minK:\n",
    "                r1=i\n",
    "            if v==maxK:\n",
    "                r2=i\n",
    "            if v<minK or v > maxK:\n",
    "                l=i\n",
    "            ans+=max(0,min(r1,r2)-l)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "        ans = 0\n",
    "        min_i = max_i = i0 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == min_k: min_i = i\n",
    "            if x == max_k: max_i = i\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "            # if j > i0: ans += j - i0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "\n",
    "\n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "            \n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx == -1 or minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx == -1 or minIdx == -1:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "            if nums[i] == minK == maxK:\n",
    "                ans += 1\n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\r\n",
    "        if minK > maxK: return 0\r\n",
    "        res = 0\r\n",
    "        lastInvalid = lastmaxK = lastminK = -1\r\n",
    "\r\n",
    "        for i, num in enumerate(nums):\r\n",
    "            if num > maxK or num < minK:\r\n",
    "                lastInvalid = i\r\n",
    "            else:\r\n",
    "                if num == minK:\r\n",
    "                    lastminK = i\r\n",
    "                if num == maxK:\r\n",
    "                    lastmaxK = i\r\n",
    "\r\n",
    "            res += max(0, min(lastminK, lastmaxK) - lastInvalid)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans=0\n",
    "        min_i=max_i=i0=-1\n",
    "        for idx,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                min_i=idx\n",
    "            if x==maxK:\n",
    "                max_i=idx\n",
    "            if x<minK or x>maxK:\n",
    "                i0=idx\n",
    "            j=min_i if min_i<max_i else max_i\n",
    "            if j>i0:\n",
    "                ans+=j-i0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        qmn = Deque() # 区间最小值对应的下标\n",
    "        qmx = Deque() # 区间最大值对应的下标\n",
    "        l = r = 0     # 区间左右端点\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            while qmn and nums[r] <= nums[qmn[-1]]:\n",
    "                qmn.pop()\n",
    "            qmn.append(r)\n",
    "            while qmx and nums[r] >= nums[qmx[-1]]:\n",
    "                qmx.pop()\n",
    "            qmx.append(r)\n",
    "            if nums[qmn[0]] == minK and nums[qmx[0]] == maxK:\n",
    "                ans += min(qmn[0], qmx[0]) - l + 1\n",
    "            # 当前[l,r]状态下的区间最小值小于 minK 或者 区间最大值大于maxK \n",
    "            # 不符合要求, 需要缩小窗口, 缩小窗口同时更新qmn 和 qmx \n",
    "            while (qmn and nums[qmn[0]] < minK) or (qmx and nums[qmx[0]] > maxK):\n",
    "                l += 1\n",
    "                if qmn and qmn[0] < l:\n",
    "                    qmn.popleft()\n",
    "                if qmx and qmx[0] < l:\n",
    "                    qmx.popleft()\n",
    "            r += 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        minidx = maxidx = -1\n",
    "        bad = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] > maxK or nums[i] < minK:\n",
    "                bad = i\n",
    "                minidx = maxidx = -1\n",
    "                continue\n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                minidx = i\n",
    "            if nums[i] == maxK:\n",
    "                maxidx = i\n",
    "            if minidx != -1 and maxidx != -1:\n",
    "                ret += min(minidx, maxidx) - bad\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\r\n",
    "        ans = 0\r\n",
    "        min_i = max_i = i0 = -1\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            if x == min_k: min_i = i\r\n",
    "            if x == max_k: max_i = i\r\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\r\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\r\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\r\n",
    "            # j = min_i if min_i < max_i else max_i\r\n",
    "            # if j > i0: ans += j - i0\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \"\"\" Sliding Window \"\"\" \n",
    "\n",
    "        lb = -1 \n",
    "        n = len(nums) \n",
    "        id_min, id_max = -1, -1 \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                id_min = i \n",
    "            if nums[i] == maxK:\n",
    "                id_max = i \n",
    "            if not (minK <= nums[i] <= maxK):\n",
    "                lb = i\n",
    "            \n",
    "            ans += max(min(id_min,id_max) - lb, 0)\n",
    "            \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        min_i = max_i = i0 = -1\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            if x == min_k: min_i = i\n",
    "\n",
    "            if x == max_k: max_i = i\n",
    "\n",
    "            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]\n",
    "\n",
    "            ans += max(min(min_i, max_i) - i0, 0)\n",
    "\n",
    "            # 注：上面这行代码，改为手动算 min max 会更快\n",
    "\n",
    "            # j = min_i if min_i < max_i else max_i\n",
    "\n",
    "            # if j > i0: ans += j - i0\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \"\"\" Sliding Window \"\"\" \n",
    "\n",
    "        lb = -1 \n",
    "        n = len(nums) \n",
    "        id_min, id_max = -float('inf'), -float('inf')\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                id_min = i \n",
    "            if nums[i] == maxK:\n",
    "                id_max = i \n",
    "            if not (minK <= nums[i] <= maxK):\n",
    "                lb = i\n",
    "            \n",
    "            if lb < min(id_min,id_max):\n",
    "                ans += min(id_min,id_max) - lb\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        \n",
    "                    \n",
    "                        ans = 0\n",
    "                        minI = maxI = i0 = -1\n",
    "                        for i,x in enumerate(nums):\n",
    "                            if minK == x:minI = i\n",
    "                            if maxK == x:maxI = i\n",
    "                            if not minK <= x <= maxK:i0 = i\n",
    "                            ans += max(min(minI,maxI) - i0,0)\n",
    "                        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        # ans = 0 \n",
    "        # min_i = max_i = i0 =-1\n",
    "        # for i,x in enumerate(nums):\n",
    "        #     if x == minK: min_i =i\n",
    "        #     if x == maxK: max_i =i \n",
    "        #     if x < minK or x > maxK :i0 =i \n",
    "        #     j = min_i if min_i < max_i else max_i\n",
    "        #     # ans += max(min(min_i,max_i)-i0,0)\n",
    "        #     if j > i0: ans += j -i0\n",
    "        # return ans \n",
    "\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1 \n",
    "        for i ,x in enumerate(nums):\n",
    "            if x == minK : min_i =i \n",
    "            if x == maxK: max_i = i \n",
    "            if x < minK or x > maxK : i0 = i  \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            if j > i0: ans += j-i0 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        qmn = Deque()\n",
    "        qmx = Deque()\n",
    "        l = r = 0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while r < n:\n",
    "            while qmn and nums[r] <= nums[qmn[-1]]:\n",
    "                qmn.pop()\n",
    "            qmn.append(r)\n",
    "            while qmx and nums[r] >= nums[qmx[-1]]:\n",
    "                qmx.pop()\n",
    "            qmx.append(r)\n",
    "            if nums[qmn[0]] == minK and nums[qmx[0]] == maxK:\n",
    "                ans += min(qmn[0], qmx[0]) - l + 1\n",
    "            while (qmn and nums[qmn[0]] < minK) or (qmx and nums[qmx[0]] > maxK):\n",
    "                l += 1\n",
    "                if qmn and qmn[0] < l:\n",
    "                    qmn.popleft()\n",
    "                if qmx and qmx[0] < l:\n",
    "                    qmx.popleft()\n",
    "            r += 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\"\"\" \n",
    "先考虑子数组中都是[minK, maxK]范围内的数的情况，这时合法的区间应包括minK和maxK，假设当前下标为右端点，则合法的左端点数量应为min(minI, maxI) + 1，其中minI表示左侧第一次出现minK的下标，同理maxI表示左侧第一次出现maxK的下标，两个边界值minK、maxK都要出现，所以是取下标的较小值min(minI, maxI)。\n",
    "由于子数组中不一定都是[minK, maxK]范围的数，所以可以用一个下标维护最后一个不是[minK, maxK]范围数的下标i0，则枚举每个右侧端点时，左侧端点的有效范围对应的数量为：min(minI, maxI) - i0，而当min(minI, maxI) < i0时，表示有效范围内不包含两个边界值，也即有效的左侧端点数量为零，这种情况跟0取max即可：最终累加答案为max(min(minI, maxI) - i0, 0)。\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        i0 = minI = maxI = -1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < minK or x > maxK:\n",
    "                i0 = i\n",
    "                continue\n",
    "            if x == minK:\n",
    "                minI = i\n",
    "            if x == maxK:\n",
    "                maxI = i\n",
    "            ans += max(min(minI, maxI) - i0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        if minK>maxK:\n",
    "            return 0\n",
    "        l,h=-1,-1\n",
    "        left=0\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if nums[i]==minK:\n",
    "                l=i\n",
    "            if nums[i]==maxK:\n",
    "                h=i\n",
    "            if nums[i]<minK or nums[i]>maxK:\n",
    "                l=-1\n",
    "                h=-1\n",
    "                left=i+1\n",
    "            if l!=-1 and h!=-1:\n",
    "                ans+=min(l,h)-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        res = 0\n",
    "        l = -1\n",
    "        minKIndex = maxKIndex = -1\n",
    "\n",
    "        for r in range(len(nums)):\n",
    "            if nums[r] == minK:\n",
    "                minKIndex = r\n",
    "            if nums[r] == maxK:\n",
    "                maxKIndex = r\n",
    "            if nums[r] > maxK or nums[r] < minK:\n",
    "                l = r\n",
    "            res += max(min(minKIndex,maxKIndex) - l, 0)\n",
    "            \n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minI, maxI, i0 = -1, -1, -1\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == minK:\n",
    "                minI = i\n",
    "            if x == maxK:\n",
    "                maxI = i\n",
    "            if not minK <= x <= maxK:\n",
    "                i0 = i\n",
    "            ans += max(min(minI, maxI) - i0, 0)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        leftMax = - 1\n",
    "        leftMin = - 1\n",
    "        leftBound = - 1 \n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == minK:\n",
    "                leftMin = i \n",
    "            if num == maxK:\n",
    "                leftMax = i \n",
    "            if num < minK or num > maxK:\n",
    "                leftBound = i \n",
    "            res += max(0, min(leftMin, leftMax) - leftBound)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans=0\n",
    "        imax=-1\n",
    "        imin=-1\n",
    "        i0=-1\n",
    "        n=len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==minK:\n",
    "                imin=i\n",
    "            if x==maxK:\n",
    "                imax=i\n",
    "            if x<minK or x>maxK:\n",
    "                i0=i\n",
    "            ans+=max(min(imax,imin)-i0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        leftMin, leftMax, leftBound = - 1, - 1, - 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == minK:\n",
    "                leftMin = i\n",
    "            if nums[i] == maxK:\n",
    "                leftMax = i\n",
    "            if nums[i] > maxK or nums[i] < minK:\n",
    "                leftBound = i \n",
    "            res += max(min(leftMin, leftMax) - leftBound, 0)\n",
    "        return res \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        # ans = 0 \n",
    "        # min_i = max_i = i0 =-1\n",
    "        # for i,x in enumerate(nums):\n",
    "        #     if x == minK: min_i =i\n",
    "        #     if x == maxK: max_i =i \n",
    "        #     if x < minK or x > maxK :i0 =i \n",
    "        #     j = min_i if min_i < max_i else max_i\n",
    "        #     # ans += max(min(min_i,max_i)-i0,0)\n",
    "        #     if j > i0: ans += j -i0\n",
    "        # return ans \n",
    "\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 = -1 \n",
    "        for i ,x in enumerate(nums):\n",
    "            if x == minK : min_i =i \n",
    "            if x == maxK: max_i = i \n",
    "            if x < minK or x > maxK : i0 = i  \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            if j > i0: ans += j-i0 \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 =-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x == minK: min_i =i\n",
    "            if x == maxK: max_i =i \n",
    "            if x < minK or x > maxK :i0 =i \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            # ans += max(min(min_i,max_i)-i0,0)\n",
    "            if j > i0: ans += j -i0\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        ans = 0 \n",
    "        min_i = max_i = i0 =-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x == minK: min_i =i\n",
    "            if x == maxK: max_i =i \n",
    "            if x < minK or x > maxK :i0 =i \n",
    "            j = min_i if min_i < max_i else max_i\n",
    "            ans += max(min(min_i,max_i)-i0,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        def counttimes(start,end):\n",
    "            l=start\n",
    "            r=start\n",
    "            cntmax=0\n",
    "            cntmin=0\n",
    "            ans=0\n",
    "            while r<=end:\n",
    "                if nums[r]==minK: cntmin+=1\n",
    "                if nums[r]==maxK: cntmax+=1\n",
    "                while cntmin and cntmax and l<=r:\n",
    "                    if nums[l]==minK: cntmin-=1\n",
    "                    if nums[l]==maxK: cntmax-=1\n",
    "                    l+=1\n",
    "                ans+=(r-start+1)-(r-l+1)\n",
    "                r+=1\n",
    "            return ans\n",
    "        start=0\n",
    "        cnt=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<minK or x>maxK:\n",
    "                cur=counttimes(start,i-1)\n",
    "                cnt+=cur\n",
    "                start=i+1\n",
    "        cnt+=counttimes(start,len(nums)-1)\n",
    "        return cnt   \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        n = len(nums)\n",
    "        start_point = 0\n",
    "        idx = ans = 0\n",
    "        min_pos = max_pos = -1\n",
    "\n",
    "        while idx < n:\n",
    "            if nums[idx] < minK or nums[idx] > maxK:\n",
    "                idx += 1\n",
    "                start_point = idx\n",
    "                continue\n",
    "            if nums[idx] == minK:\n",
    "                min_pos = idx\n",
    "            if nums[idx] == maxK:\n",
    "                max_pos = idx\n",
    "\n",
    "            if min_pos <= max_pos:\n",
    "                t = min_pos - start_point + 1\n",
    "            else:\n",
    "                t = max_pos - start_point + 1\n",
    "            if t < 0:\n",
    "                t = 0\n",
    "            ans += t\n",
    "            idx += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:\n",
    "        minIdx = -1\n",
    "        maxIdx = -1\n",
    "\n",
    "        start = -1\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < minK or nums[i] > maxK:\n",
    "                start = -1\n",
    "                minIdx = -1\n",
    "                maxIdx = -1\n",
    "                continue\n",
    "\n",
    "            if start == -1:\n",
    "                start = i \n",
    "\n",
    "            if nums[i] == minK:\n",
    "                minIdx = i \n",
    "            \n",
    "            if nums[i] == maxK:\n",
    "                maxIdx = i\n",
    "            \n",
    "            if nums[i] == minK:\n",
    "                if maxIdx != -1:\n",
    "                    ans += maxIdx - start + 1\n",
    "            elif nums[i] == maxK:\n",
    "                if minIdx != -1:\n",
    "                    ans += minIdx - start + 1\n",
    "            else: # middle\n",
    "                if maxIdx != -1 and minIdx != -1:\n",
    "                    ans += min(maxIdx, minIdx) - start + 1 \n",
    "\n",
    "\n",
    "\n",
    "                   \n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
